1. Field of the Invention
The present invention relates to a technique for composing three-dimensional multi-viewpoints data obtained by measuring a three-dimensional object from a plurality of directions and/or distances.
2. Description of the Background Art
There are two methods of composing three-dimensional multi-viewpoints data obtained by measuring a three-dimensional object from a plurality of directions, i.e., xe2x80x9cpolygon-based methodxe2x80x9d and xe2x80x9cvolumetric methodxe2x80x9d. Both these methods are used for composing a plurality of original data obtained by measuring an object from a plurality of viewpoints (i.e, viewing points), and the original data are referred to as xe2x80x9cpolygon mesh dataxe2x80x9d.
Prior to discussion on these methods, polygon mesh data will be discussed. A camera capable of measuring a three-dimensional shape of an object is sequentially set at a plurality of positions of viewpoints. Data obtained by the camera at the viewpoints are converted into range images representing a range from the camera to parts of the object with reference to camera parameter values.
The range image is a set of latticed discrete points, and three-dimensional coordinate value data are defined at each lattice point. In the range image having this data structure, each point is connected to its adjacent four points in four directions by segments, to form a square polygon or a triangular polygon. In each polygon, a direction towards a viewpoint in obtaining a range image is defined as an upward direction. A set of polygons thus obtained is a polygon mesh data. Since the polygon mesh data are obtained for each viewpoint, the number of polygon mesh data is equal to the number of viewpoints.
The polygon-based method will be discussed below. In this method, two of polygon mesh data obtained from a number of viewpoints are sewn together to compose one polygon mesh data. By sewing each pair of adjacent polygon mesh data, all the polygon mesh data are composed, to eventually obtain one composed polygon mesh data.
Two polygon mesh data are composed as below. When polygons in the respective meshes defined by two polygon mesh data are overlapped, one of these polygons is deleted. After that, one of these meshes is clipped on the other.
FIGS. 12 to 14 are illustrations showing a clipping of meshes. In these figures, for explanatory convenience, meshes 31 and 32 are assumed on the same plane. Referring to FIGS. 12 to 14, the clipping of meshes will be discussed below.
First, as shown in FIG. 12, intersections 33 between respective boundaries of the mesh 31 and edges of the mesh 32 are created. With the intersections 33 as boundaries, an unnecessary disposal region 34 as shown in FIG. 13 is deleted, and a set of intersections 33 are connected to vertexes on the boundaries of the mesh 32, to form triangular polygons shared by the meshes 31 and 32. As a result, as shown in FIG. 14, a composed mesh 35 is obtained by composing the meshes 31 and 32.
Thus, clipping of meshes is performed as the boundary of two meshes is zippered to form a new polygon, filling a clearance.
The polygon-based method is disclosed, in detail, for example, in Greg Turk and Mark Levoy, xe2x80x9cZippered Polygon Meshes From Range Imagesxe2x80x9d. Proceedings of ACMSIG GRAPH ""94, pp. 311 to 318. ACM Press, 1994.
Next, the volumetric method will be discussed. In the volumetric method, three-dimensional space is divided into grids of a small unit in x, y and z directions and a small cube of unit grid, i.e., voxel, is used. For example, a rectangular pyramid 21 shown in FIG. 15A is represented by using a number of voxels 22 as shown in FIG. 15B.
With respect to each of the above voxels, a potential value corresponding to a range from a polygon defined by the polygon mesh data to the voxel, is determined.
For example, when the voxel 22, a viewpoint 23 and a mesh 24 are positioned as shown in FIG. 16, a potential value is determined on the basis of a distance dx from the voxel 22 on a line of sight 25 to a point x in a polygon 26 of the mesh 24. In such a case, in general, when the voxel 22 is positioned on a side of the viewpoint 23 with respect to the polygon 26, the potential value is negatively signed and when positioned on an opposite side of the viewpoint 23, the value is positively signed. Therefore, in the example of FIG. 16, the potential value is negatively signed.
Since the above calculation of the potential value is executed with respect to a plurality of polygon mesh data obtained from a number of viewpoints, usually, a plurality of potential values are obtained for each voxel. The sum of those potential values is an added potential value for each voxel.
Then, polygon mesh data are generated again by using Marching Cubes algorithm and the like on the basis of the added potential value for each voxel.
The volumetric method is disclosed, in detail, for example, in Brian Curless and Marc Levoy, xe2x80x9cA Volumetric Method For Building Complex Models From Range Imagesxe2x80x9d Computer Graphics, Annual Conference Series, pp. 303 to 312, 1996 (Proceedings Siggraph ""96).
As discussed above, composition of a plurality of polygon mesh data, i.e., original data obtained from a number of viewpoints is conventionally performed by using the polygon-based method or the volumetric method.
Since in the polygon-based method, as discussed above, two of the original polygon mesh data are sequentially composed to eventually obtain one composed polygon mesh data, if any of the original polygon mesh data includes some inaccuracies such as errors, the effect directly appears in the composed polygon mesh data. It is impossible to get rid of these inaccuracies from the composed polygon mesh data.
Further, the composed polygon mesh data are sensitive to errors in the original polygon mesh data and those generated in registration of a plurality of original polygon mesh data on a coordinate system. Especially, such a shape as a thin stick, sensitive to even a small error, cannot! be restructured with the composed polygon mesh data.
Furthermore, since it is necessary to reconstruct a segment connecting two points, i.e., a phase every time when two original polygon mesh data are composed, as the multiplicity of the original polygon mesh data, which is in proportion to the number of polygon elements constituting a mesh, becomes larger, a processing efficiency becomes lower.
On the other hand, in the volumetric method, since the sum of a plurality of potential values is the added potential value for each voxel, an error of one original polygon mesh data and that of other data offset each other in many cases, and therefore some inaccuracies of the original polygon mesh data have few effects. As a result, even higher multiplicity of the original mesh data hardly reduces the processing efficiency. In other words, the volumetric method can resolve all the problems of the polygon-based method.
Since the size of voxel is uniform, however, in the volumetric method, the resolution of the eventually-obtained composed polygon mesh data becomes uniform on the whole. Therefore, when the size of voxel is made small in accordance with a portion of high resolution among a plurality of polygon mesh data obtained from a number of viewpoints, the composed polygon mesh data have high redundancy to deteriorate efficiency of calculation. When in accordance with a portion of low resolution, high-resolution data of the original data are lost.
Further, when the potential value is calculated for each voxel, the polygon mesh data are resampled, and when faces of each voxel, i.e., polygons are extracted on the basis of the added potential value, interpolated vertexes are calculated. These two calculations inevitably cause deterioration in accuracy. To maintain the accuracy in the volumetric method, it is necessary to, set the size of voxel at a small value, and as mentioned above, that gives the composed polygon mesh data too high redundancy and requires a larger amount of all and is impractical.
The present invention is directed to a method of composing a plurality of three-dimensional data obtained by measuring an object from a number of viewpoints. The plurality of three-dimensional data define a plurality of original meshes representing a plurality of surface images of said object observed from different directions and/or distances. According to a first aspect of the present invention, the method comprises the steps of: (a) converting the plurality of original meshes into a first surface mesh through a volumetric method; and (b) correcting a mesh structure of the first surface mesh by comparing the first surface mesh with the plurality of original meshes, to thereby obtain a second surface mesh; and (c) correcting a local position of the second surface mesh by comparing the second surface mesh with the plurality of original meshes, to thereby obtain a third surface mesh. In the method of the first aspect, each mesh is defined by a set of polygons, and a composed result of the plurality of three-dimensional data is given by data representing the third surface mesh.
In the method of the first aspect of the present invention, since the first surface data are obtained through the volumetric method using the voxels in the step (a), the first surface data can be obtained with stability even if the plurality of original three-dimensional data have some errors.
Moreover, since the mesh structure and position of the first surface mesh is corrected by referring to relevant parts of the plurality of original meshes, the resolution of the original data can be maintained. As a result, it is not necessary to reduce the size of voxel, causing unnecessarily high redundancy, and therefore it is possible to suppress a time required for the step (a) to a practical level.
Further, a composed result with high accuracy, on which the positional accuracy of the original data is reflected, can be obtained.
In short, by the method of composing the three-dimensional multi-viewpoints data of the first aspect of the present invention, the third surface mesh can be obtained as a composed result with stability even if the original three-dimensional data have some errors within a time of practical level, without unnecessarily high redundancy of the surface data obtained by the step (a), while the accuracy and resolution of the original three-dimensional data obtained from a number of viewpoints are maintained.
According to a second aspect of the present invention, in the method, the step (b) includes the steps of (b-1) sequentially selecting one of vertexes of the first surface mesh as a first objective vertex; (b-2) selecting a reference mesh from the plurality of original meshes with respect to the first objective vertex; and (b-3) correcting a structure of the first surface mesh surrounding the first objective vertex according to a resolution of the reference mesh, to obtain the second surface mesh.
Preferably, the step (b-2) includes the steps of (b-2-1) selecting reference meshes existing within a first threshold distance from the first objective vertex, out of the plurality of original meshes; (b-2-2) determining the highest one of resolutions of the reference meshes as a reference resolution; and (b-2-3) correcting the mesh structure of the first surface mesh surrounding the first objective vertex according to the reference resolution.
In the method of the second aspect of the present invention, it is possible to omit an original mesh that is unnecessarily away from the first objective vertex and is unreliable.
Further, since the highest resolution among the resolutions of the plurality of original meshes is selected, high resolution of the second surface mesh is ensured.
According to a third aspect of the present invention, in the method, the step (c) includes the steps of (c-1) sequentially selecting one of vertexes of the second surface mesh as a second objective vertex; (c-2) selecting a reference portion from the plurality of original meshes with respect to the second objective vertex; and (c-3) correcting a relative position of the second objective vertex with respect to the reference portion, to obtain the third surface mesh.
Preferably, the step (c-2) includes the steps of (c-2-1) selecting mesh elements existing within a second threshold distance from the second objective vertex, out of the plurality of original meshes; and (c-2-2) moving the second objective vertex to reduce a sum of distances from the second objective vertex to the mesh elements.
Since part of the plurality of original meshes whose distance from the second objective vertex is relatively small is referred to, correction is not based on another part that is excessively away from the second objective vertex and unreliable.
Further, since the sum of distances from the second objective vertex to the mesh elements is reduced, a composed result with high accuracy on which the shape of the original three-dimensional data is most reflected can be obtained.
Preferably, the step (c-2-2) includes the step of moving the second objective vertex to minimize the sum of distances from the. second objective vertex to the mesh elements.
Preferably, the step (c-2-2) includes the step of moving the second objective vertex so that the sum of distances from the second objective vertex to the mesh elements is smaller than a predetermined threshold value.
According to a fourth aspect of the present invention, in the method, the step (c-2-1) includes the step of determining whether or not the plurality of original meshes have a facing polygon which faces to the second objective vertex; adding the facing polygon to the mesh elements when the plurality of original meshes have the facing polygon; and adding a vertex corresponding to the second objective vertex among vertexes of the plurality of original meshes to the mesh elements when the plurality of original meshes have no facing polygon.
The resolution of the composed result can be thereby made closer to that of the selected original mesh.
The present invention is also directed to an apparatus and a computer software product suitable to perform the above method.
An object of the present invention is to obtain composed polygon mesh data with little effect of errors of the original data, within a time of practical level, without unnecessarily high redundancy.
Another object of the present invention is to maintain the accuracy and resolution of the original three-dimensional data obtained from a number of viewpoints in the composed polygon mesh data.